#define _CRT_SECURE_NO_WARNINGS
#include"tree.h"
#include"queue.h"
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a,int* pi)
{
	if (a[*pi] == '#') return NULL; 
	BTNode* root =(BTNode*)malloc(sizeof(BTNode));
	root->data = a[(*pi)++];
	root->left = BinaryTreeCreate(a, pi);
	root->right= BinaryTreeCreate(a, pi);
	return root;
}
// 二叉树销毁
void BinaryTreeDestroy(BTNode** root)
{
	if (root == NULL)return;
	BTNode* new = *root;
	BinaryTreeDestroy(&new->left);
	BinaryTreeDestroy(&new->right);
	free(new);
	*root = NULL;
}
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)return 0;
	return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)return 0;
	if (root->left == NULL && root->right == NULL)return 1;
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)return 0;
	if (k == 1)return 1;
	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)return NULL;
	if (root->data == x)return root;
	BTNode* left = BinaryTreeFind(root->left, x);
	if (left != NULL)return left;
	BTNode* right = BinaryTreeFind(root->right, x);
	if (right!= NULL)return right;
	return NULL;
}
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)return ;
	printf("%d", root->data);
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);
}
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)return;
	BinaryTreeInOrder(root->left);
	printf("%d", root->data);
	BinaryTreeInOrder(root->right);
}
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)return;
	BinaryTreePostOrder(root->left);
	BinaryTreePostOrder(root->right);
	printf("%d", root->data);
}
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{ 
		QueuePush(&q, root);
		while (!QueueEmpty(&q))
		{
			BTNode* front = QueueFront(&q);
			QueuePop(&q);
			printf("%d", front->data);
			if (front->left) QueuePush(&q, front->left);
			if (front->right) QueuePush(&q, front->right);
		}
	}
	QueueDestroy(&q);
}
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
		while (!QueueEmpty(&q))
		{
			BTNode* front = QueueFront(&q);
			QueuePop(&q);
			if (front == NULL)break;
			else
			{
				QueuePush(&q, front->left);
				QueuePush(&q, front->right);
			}
		}
		while (!QueueEmpty(&q))
		{
			BTNode* front = QueueFront(&q);
			QueuePop(&q);
			if (front)
			{
				QueueDestroy(&q);
				return false;
			}
			QueueDestroy(&q);
			return true;
		}
	}
}
	
